/*
 * Author: Yuan Li
 * Title: 15123 Summer session lab2
 * Date: Aug 9 2011
 */



/*	--------------------------------------------------------------------------------------------------
	lab-02 Starter Code By Kun Qian (edited by hoffman 9/6/'09) changed 50000 to 30000
*/


#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h> /* toupper() function and others */
#include "lab-03.h"

#define MAX_WORDLEN 50
#define MAX_WORDS   30000 /* Don't change this or you might overflow your allotted stack space. */
#define true 1
#define false 0

/*UNIT test switch */
#define UNIT false


/* Use the following Macros to print EVERYTHING while executing the menu function */

/* Menu print */
#define printMenu() printf("\nChoose: 'P'rint, 'S'earch, 'I'nsert, 'R'emove, 'C'ount, 'Q'uit :")
#define optP() printf("You chose to 'P'rint:\n")
#define optS() printf("Enter word to 'S'earch:\n")
#define optI() printf("Enter word to 'I'nsert:\n")
#define optR() printf("Enter word to 'R'emove:\n")
#define optC() printf("You chose to 'C'ount:\n")
#define optQ() printf("You chose to 'Q'uit:\n")

/* Insert print */
#define printInserted(word) printf("%s was successfully inserted.\n", word)
#define printFailedToInsert(word) printf("Duplicate found, %s was not inserted.\n", word)

/* Remove print */
#define printRemove(word) printf("%s was successfully removed.\n", word)
#define printFailedToRemove(word) printf("%s cannot be found, and was not removed.\n", word)

/* Search print */
#define printFound(word) printf("%s was successfully found.\n", word)
#define printNotFound(word) printf("%s was not found.\n", word)

/* Count print */
#define printCount(count) printf("%d words currently in the dictionary.\n", count)

/* my defined type */
typedef struct{
	int index;
	int retVal;
	int flag;
} searchResult;

char** dictionary;

/*  Some of my small helper function: */

/*
 * freeHeap -- free the space which alloc by malloc
 * dictionary -- address of dictionary
 * count -- keep track of how many words stored at the dictionary
 */
void freeHeap(char** dictionary, int count)
{
	int index;
	/* first, free the word trunks */
	for (index=0;index < count; index++){
		free(dictionary[index]);
	}

	/* second, free the dictionary */
	free(dictionary);

	return;
}


/*
 * resize -- will double dictionary size
 * @param count -- keep track of number of words in the dictionary
 * @return -- return 0, if resize fails, otherwise return new size of dictionary
 */
 int resize(int count)
{
	int index;
	int size = 2*count;
	char** tmp = malloc(size*sizeof(char*));

	/* check malloc operation */
	if (tmp == NULL)
		return 0;

	/* copy the words from the old trunk to resize trunk*/
	for(index=0; index < count; index++){
		tmp[index] = dictionary[index];
	}

	/* free the old trunck */
	free(dictionary);
	/* get new trunck */
	dictionary = tmp;
	
	return size;
}

/*
 * Binsearch -- will search the dictionary in log n 
 * @param result -- address of struct to store return value
 * @param start -- start point of search range
 * @param end -- end point of search range
 * @param word -- the given word need to search
 */
void BinSearch(searchResult* result, int start, int end, char* word)
{
	int retVal;
	int middle;

	/* maybe need some checks for input parameters*/
	if (start > end){
		printf("start > end at binary search\n");
		/* may not free the heap, but it does not matter */
		exit(EXIT_FAILURE);
	}
	/**********************************************/

	/* Base case */
	if (start == end){
		retVal = strcmp(word,dictionary[start]);
		if (retVal == 0){
			result->flag = true;
			result->retVal = retVal;
			result->index = start;
			return;
		}
		else{
			result->flag = false;
			result->retVal = retVal;
			result->index = start;
			return;
		}	
	}

	/* Recursive case */
	middle = start + (end-start)/2;

	retVal = strcmp(word,dictionary[middle]);
	
	if (retVal == 0){
		result->flag = true;
		result->retVal = retVal;
		result->index = middle;
		return;
	}
	else if (retVal > 0){
		BinSearch(result, middle+1, end, word);
		return;
	}
	else{
		if ((middle-1) < start)
			BinSearch(result, start, start, word);
		else
			BinSearch(result, start, middle-1, word);
		
		return;
	}
}

/*
 * shiftWord -- will shift words in the dictionary backward 1 position
 * @param start -- shift from this index
 * @param count -- keep track of the words in the dictionary
 */
void shiftWord(int start, int count)
{
	int index;
	char* prev;
	char* curr;

	prev = dictionary[start];
	for (index=start; index < count; index++){
		curr = dictionary[index+1];
		dictionary[index+1] = prev;
		prev = curr;
	}

	return;
}

/**************************************/

/* From the menu this gets called everytime the user selects 'P'rint. In this case you just pass in stdout
    for the stream arg.  If the user type 'Q'uit then you must first open up the output file and pass in the
    file handle.  Be sure to close that file as soon as this function is done. */


/* printDictionary -- print out the 2D dictionary to a specific stream
 * @param cnt -- the variable which indicates the how many words stored in the dictionary
 * @param stream -- the stream need to print to
 */
void printDictionary(int cnt, FILE *stream )
{	int row;
	int wordcnt = 0;
	for (row=0; row < cnt; row++){
		/* if it reaches the line length limitation */
		if ((wordcnt+strlen(dictionary[row])) > 80){
			fprintf(stream, "\n");
			/* clear wordcnt for a newline*/
			wordcnt = 0;
		}
		fprintf(stream, "%s ", dictionary[row]);
		/* accumulate wordcnt plus space */
		wordcnt = wordcnt + strlen(dictionary[row]) + 1;
	}
	
	return;
}

/*
 * searchWord -- will return true if the given is found in the dictionary, vice versa 
 * @param count -- address of variable which keep track of numbers of word in the dictionary
 * @param word -- a given word need to find out
 */ 
void searchWord(int count, char *word)
{
	searchResult result;

	BinSearch(&result, 0, count, word);
	if (result.flag == true){
		printFound(word);
		return;
	}
	else{
		printNotFound(word);
		return;
	}
}

/*
 * insertWord -- insert a new word into the dictionary
 * @param count -- the address of variable which indicates numbers of words in the dictionary
 * @param size -- the size of the dictionary
 * @param word -- the word need to insert
 * @param verbose -- flag which indicate whether to print some words
 */

void insertWord(int *count, int *size, char *word, int verbose)
{
	/* maybe need steps to exam the input whether the args is valid address before use them*/
	searchResult result;

	/* check whether the dictionary is full */
	if (*count == *size){
		*size = resize(*count);
		if (*size == 0){
			printf("fail to resize the dictioanry\n");
			exit(EXIT_FAILURE);
		}
	}

	/* if the dictionary is empty, just insert this word */
	if (*count == 0){
		dictionary[0] = word;
		(*count)++;
		if (verbose)
			printInserted(word);
		return;
	}

	/* we should not generate duplicate word in the dictionary */
	BinSearch(&result, 0, *count-1, word);
	if (result.flag == true){
		if (verbose)
			printFailedToInsert(word);
		free(word);
		return;
	}


	/* insert the word */
	if (result.retVal > 0){
		shiftWord(result.index+1, *count);
		dictionary[result.index+1] = word;
		(*count)++;
		if (verbose)
			printInserted(word);
		return;
	}
	/* result.retVal < 0 */
	else{
		shiftWord(result.index, *count);
		dictionary[result.index] = word;
		(*count)++;
		if (verbose)
			printInserted(word);
		return;
	}
	/* should not get here */
	fprintf(stdout,"Error happened at insertWord!\n");
}

/*
 * removeWord -- will remove a given a word from the dictionary, then shift up all the words
 * 			behind it a position
 * 	@param count -- address of variable which keep track of number of words in the dictionary
 * 	@param word -- the word need to be removed
 */
void removeWord(int *count, char *word )
{
	int index;

	searchResult result;
	BinSearch(&result, 0, *count-1, word);
	if (result.flag == false){
		printFailedToRemove(word);
		return;
	}
	else{
		free(dictionary[result.index]);
		for (index=result.index; index < *count; index++){
			dictionary[index] = dictionary[index+1];
		}
		printRemove(word);
		(*count)--;
		return;
	}

}

/*
 * countWord -- will display how many words stored in the dictionary
 * @param count -- address of variable which keep track of number of words in the dictionary
 */
void countWord(int count)
{
	printCount(count);
	return;
}

/*
 * quit -- will print out the dictionary to the specific file, then quit the program
 * @param count -- address of variable which keep track of number of words in the dictionary
 * @param outfileName -- name of output file
 */
void quit(int count, char *outfileName )
{
	FILE* output;

	/* open the file and check the failure */
	output = fopen(outfileName, "wt");
	if (output == NULL){
		printf("fail to open the output file %s\n", outfileName);
		exit(EXIT_FAILURE);
	}

	printDictionary(count, output);
	fclose(output);
	return;
}


/* LOADDICTIONARY
 * loadDictionary -- will load a banch of words from a file to a 2D dictionary array in order
 * @param infilname -- the file which read from
 * @param count -- address of the variable which keep track of numbers words in the dictionary
 * @param size -- the size of the dictionary
 */
void loadDictionary( char *infilname, int *count, int *size)
{
	FILE* infile;
	char* wordBuffer;
	
	/* open the file, fopen will return a pointer for that file, return NULL if fails to open */
	infile = fopen(infilname, "rt");
	if (infile == NULL){
		fprintf(stderr,"fail to open file %s\n!",infilname);
		exit(EXIT_FAILURE);
	}

	while(fgetline_123(&wordBuffer, infile) != NULL){
		insertWord(count, size, wordBuffer, false);
	}

	/* close the file before return */
	fclose(infile);
	return;
}


/* Other than the printf calls above in the macros, and the ones we put into main,
	you should not call printf anywhere else.

	You DO need fprintf in your printDictionary
*/

/*
 * doMenu -- is infinite loop which waits for the user's input, then gives response
 * @param outfileName -- the name of the file to output
 * @param count -- address of variable which keeps track of number of word in the dictionary
 * @param size -- address of variable which indicate the size of dictionary
 */

void doMenu( char *outfileName, int *count, int *size)
{
	char ch;
	char* wordBuffer;
	while (true){
		printMenu();
		/* reader a charactor(choice) from keyboard 
		 * %* will eat up the all reminder charactor
		 * [^\n] will stop the scan when encounter a newline
		 * getchar() will eat the newline
		 */
		if (scanf(" %c%*[^\n]", &ch) == 0){
			printf("Error happened at scanf!\n");
			exit(EXIT_FAILURE);
		}	
		getchar();

		/* choice handle */
		if (ch == 'P'){
			optP();
			printDictionary(*count, stdout);
			printf("\n");
		}
		else if (ch == 'S'){
			optS();
			fgetline_123(&wordBuffer, stdin);
			searchWord(*count, wordBuffer);
			free(wordBuffer);
		}
		else if (ch == 'I'){
			optI();
			fgetline_123(&wordBuffer, stdin);
			insertWord(count, size, wordBuffer, true);
		}	
		else if (ch == 'R'){
			optR();
			fgetline_123(&wordBuffer, stdin);
			removeWord(count, wordBuffer);
			free(wordBuffer);
		}
		else if (ch == 'C'){
			optC();
			countWord(*count);
		}
		else if (ch == 'Q'){
			quit( *count, outfileName);
			return;
		}
		else{
			printf("unknow choice!!\n");
		}	

	}	
}

/*    M A I N   F U N C T I O N  */
#if UNIT == false
int main( int argc, char *argv[] )
{
	time_t startTime, stopTime;
	clock_t startCPU, stopCPU;
	double elapsedCPUsecs;

	/* char dictionary[MAX_WORDS][MAX_WORDLEN], instead of setup a static array
	 * we setup a dynamic array with initial size 50 words
	 */
	int count=0;
	int size =50;
	dictionary = malloc(50*sizeof(char*));

	/* check malloc operation */
	if (dictionary == NULL){
		printf("malloc failed at the initialization stage!\n");
		freeHeap(dictionary, count);
		return EXIT_FAILURE;
	}

	if (argc < 3 )
	{
		printf("usage: ./%s <infileName> <outFilename>\n",argv[0]);
		return EXIT_FAILURE;
	}

	startTime = time( NULL );
	printf("\nStarting load of %s at %s", argv[1], ctime( &startTime) );

	startCPU = clock();
	loadDictionary(argv[1], &count, &size);
	stopCPU = clock();
	stopTime = time( NULL );
	printf("Finished load of %s at %s", argv[1], ctime( &stopTime) );
	elapsedCPUsecs = ((double)(stopCPU-startCPU)) / CLOCKS_PER_SEC;
	printf("Elapsed CPU seconds: %f\n",  elapsedCPUsecs );

	doMenu( argv[2], &count, &size);
	freeHeap(dictionary, count);
	return EXIT_SUCCESS; /* EXIT_SUCCESS defined as 0 in stdlib.h */
}
#endif



/* unit test */


#if UNIT == true
int main(int argc, char **argv)
{
	int count=0;
	int size =50;

	dictionary = malloc(50*sizeof(char*));
	/* test case for printDictionary and searchDuplicate function
	printf("for a empty dic to call searchDuplicate:1 for true, 0 for false\n%d\n",\
			searchDuplicate(dictionary, count, "hello"));
	strcpy(dictionary[0], "hello");
	strcpy(dictionary[1], "world");
	strcpy(dictionary[2], "test");
	strcpy(dictionary[3], "apple");
	count = 4;
	printDictionary(dictionary,count,stdout);
	printf("search \"test\":%d\n",searchDuplicate(dictionary, count, "test"));
	printf("search \"app\":%d\n",searchDuplicate(dictionary, count, "app"));
	*/

	/* test loadDictionary 
	loadDictionary(argv[1], dictionary, &count);
	printDictionary(dictionary, count, stdout);
	printf("%d\n",count);
	*/

	/* test removeWord 
	removeWord(dictionary, &count, "waits");
	printf("%d\n",count);
	removeWord(dictionary, &count, "lenove");
	printf("%d\n",count);
	printDictionary(dictionary, count, stdout);
	*/

	/* test fgetline_123
	char* line;
	if (fgetline_123(&line,stdin) == NULL){
		printf("nothing read from kb!!\n");
		free(line);
		return 0;
	}
	else{
		printf("get %s from kb\n",line);
		free(line);
		return 0;
	}
	*/

	/* test BinSearch,first comment out test loadDictionary 
	BinSearch(&result, dictionary, 0, count, "zymosis");
	if (result.flag == true){
		printf("find the word: %s\n", dictionary[result.index]);
	}
	else
		printf("not find the word\n");
		*/

	/* test loadDictionary */
	loadDictionary(argv[1], &count, &size);
	printf("count=%d\n",count);
	printDictionary(count, stdout);

	return 0;
}
#endif
